Rate distortion coding relates to a trade-off between communication fidelity and communication rate, where the required rate can be reduced by accepting decreased fidelity. For the special case of loss-less coding, i.e., without distortion, the minimum required communication rate is known to be the source entropy rate, and practical universal methods of lossless coding are known that provide performance at or near this limit.
When data is compressed using a loss-less method, it is possible to reconstruct the original format without losing information. Such a non-distorting compression mode is exemplified by the Lempel-Ziv method (Ziv & Lempel, 1977). Lossless compression ensures complete data fidelity and zero distortion after image or data reconstruction, which is generally very important in many scientific and medical applications such as medical imaging, image archiving, remote sensing and such, but generally requires a significant amount of costly memory and storage capacity.
As an alternative to the use of lossless compression, a lossy coding technique, i.e. non-zero distortion, may be employed The use of lossy compression results in some loss of information, in some distortion and, therefore, in reduced information fidelity to some degree, but carries the benefit of considerably reduced storage and memory requirements and costs. In contrast to medical and scientific applications where high information fidelity is critical, applications in multimedia systems, such as TV, video (images in motion), photography (still images), can tolerate incomplete information fidelity.
In recent years, there has been progress towards designing universal lossy compressor especially in trying to tune some of the existing universal loss-less coders to work in the lossy case as well. In Kontoyiannis I, 1999, a lossy version of Lempel-Ziv algorithm at fixed distortion is rendered, and is shown to be optimal for memoryless sources.
Practical universal methods for lossy coding are needed, that provide performance at or near the rate-distortion limit, as imposed by the source statistics.